1. Field of the Invention
This invention relates to generation of linear recurring sequences and the utilization of such sequences.
2. Relevant Background
Definitions
Asynchronous Transfer Mode (ATM): a communications protocol with a 384 bit data frame (payload) size.
Bit Error Rate Test (BERT) equipment: tests for errors by outputting a long stream of pseudorandom bits onto the communication line. The communication line is looped back to the BERT so that the same bits that it sends out should return to it. The BERT then compares the return bits to find any bits that are altered while they traveled over the communication line.
Characteristic Polynomial: usually associated with the Galois form of LFSR. Inverse of the feedback polynomial.
Companion matrices: a linear algebraic characterization of an LFSR function that allows manipulation of linear feedback shift registers using matrix arithmetic.
Decimate: to replace an integer sequence, S={S1, S2, S3, . . . , S2nxe2x88x921}, with the sequence Sk={Sk1, S2k(mod 2n), S3k(mod 2n), S4k(mod 2n), . . . , Sk(2nxe2x88x921)(mod 2n)}, thereby producing a sequence of every Kth element of the main sequence S. When all the decimations of a sequence are combined in proper order, the original sequence S can be reconstructed. If the decimations are in parallel, the amount of time it takes to generate S is reduced by a factor of k.
Decimation Matrix: is a companion matrix raised to a power k, corresponding to a xe2x80x9cjumpxe2x80x9d in the number of states spanned by each multiplication mod 2 of the companion matrix.
Feedback Polynomial: inverse of characteristic polynomial. Usually associated with the Fibonacci form of LFSR.
Irreducible Polynomial: is a polynomial that cannot be expressed as the product of two other polynomials except for 1 and itself.
Linear Feedback Shift Register (LFSR): a type of shift register incorporating linear feedback of the present contents of the register to determine future contents of the register.
Linear Recurring Sequences (LRS): are pseudorandom sequences of digits derived from linear difference equations. A binary LRS is a sequence of 1""s and 0""s.
Linear Recurring Sequence Generator (LRSG): incorporates at least one linear feedback shift register or equivalent circuitry to produce a linear recurring sequence.
Modulo 2 (mod 2) arithmetic: is base two arithmetic where a=b(mod 2) if a=bxe2x88x92kn for k=some integer and n=2. Mod 2 addition can be represented in hardware by the XOR function; Mod 2 multiplication can be represented in hardware by the AND function.
Period: The period of a linear recurring sequence is the number of digits before the sequence begins to repeat itself.
Primitive Polynomial: is an irreducible polynomial that divides x2nxe2x88x921+1 but not xd+1 for any d that divides 2nxe2x88x921.
Pseudonoise Generator: outputs a pseudonoise signal. For digital spread spectrum communications, the pseudonoise signal is a pseudorandom sequence of 1""s and 0""s (in other words, the output of a binary LRS).
Pseudonoise Signal: is noise that appears to be random but is not truly random.
Pseudorandom Sequence: a sequence of numbers that appears to be random when viewed over a limited range but is not truly random. At some point, the sequence will repeat itself.
Stream Ciphers: a type of cipher that encrypts a message one bit at a time.
Linear Recurring Sequences
A linear recurring sequence is a pseudorandom sequence of length L with the property that every n successive bits (n less than L) appears only once in the sequence. For example, the sequence 0111010, which is discussed in detail hereinafter, is an LRS for nxe2x89xa73. It is not a LRS for n=2, as the 2 bit sequence xe2x80x9c11xe2x80x9d appears as both the second and third bits and the third and fourth bits.
FIG. 1 shows a circular representation of the aforementioned LRS. Every combination of bits covered by the 3 bit window is unique. This circular model is useful because it emphasizes that an LRS is a pseudorandom sequence and at some point will begin to repeat itself. If a linear feedback shift register (discussed below), or its equivalent, ever becomes loaded entirely with zeros, it will only output zeros.
Many applications require the ultra-fast generation of an LRS which does not repeat for a long time. One such application is in Bit Error Rate Test (BERT) equipment for testing error statistics of communication lines. Another use is in communications encryption. For example, a linear recurring sequence can be used to feed a nonlinear encryption function, creating a keystream which is used to encrypt plaintext. An LRS is also conventionally used as the pseudonoise source in spread spectrum communications.
Linear Feedback Shift Registers
Linear recurring sequences are often implemented in hardware through the use of Linear Feedback Shift Registers (LFSR). As is known in the art, an LFSR is typically implemented using either the Fibonacci (FIG. 2) or Galois (FIG. 3) model of LFSR. The Fibonacci model is characterized by the input to the first delay element being a linear combination of signal taps at various other cells in the register. The Galois model is characterized by the input to the various cells being a linear combination of the output of the last cell and the previous cell. Each of these models can produce binary sequences having a very large period and excellent pseudorandom properties. While the Fibonacci and Galois shift registers can implement the same recurrence relation, the same sequence is generated only if each is started in the appropriate initial state.
Each LFSR can be described advantageously by a companion matrix. Because LFSRs can be either right-shifting or left-shifting, a companion matrix will take one of two general forms.                     [                                                            C                                  n                  -                  1                                                                    ⋯                                      ⋯                                                      C                1                                                                    C                0                                                                        1                                      0                                      ⋯                                      0                                      0                                                          0                                      1                                      0                                      ⋯                                      0                                                          ⋯                                      ⋯                                      ⋯                                      ⋯                                      ⋯                                                          0                                      ⋯                                      ⋯                                      1                                      0                                      ]                              Left  Shifting  Galois  (M1)                ⁢                  xe2x80x83                      ⁢          xe2x80x83        ⁢                  [                                            0                                      ⋯                                      ⋯                                      0                                                      A                0                                                                        1                                      0                                      ⋯                                      0                                                      A                1                                                                        0                                      1                                      0                                      ⋯                                      ⋯                                                          ⋯                                      ⋯                                      ⋯                                      ⋯                                      ⋯                                                          0                                      ⋯                                      ⋯                                      1                                                      A                                  n                  -                  1                                                                    ]                              Left  Shifting  Fibonacci  (M2)                ⁢                  xe2x80x83                                        [                                            0                                      1                                      ⋯                                      0                                      0                                                          0                                      0                                      1                                      ⋯                                      0                                                          0                                      ⋯                                      ⋯                                      ⋯                                      0                                                          0                                      ⋯                                      ⋯                                      0                                      1                                                                          C                0                                                                    C                1                                                    ⋯                                      ⋯                                                      C                                  n                  -                  1                                                                    ]                              Right  shifting  Galois  (M3)                ⁢                  xe2x80x83                      ⁢          xe2x80x83        ⁢                  [                                                            A                                  n                  -                  1                                                                    1                                      ⋯                                      0                                      0                                                          ⋯                                      ⋯                                      ⋯                                      ⋯                                      ⋯                                                          ⋯                                      ⋯                                      0                                      1                                      0                                                                          A                1                                                    0                                      ⋯                                      0                                      1                                                                          A                0                                                    0                                      0                                      0                                      0                                      ]                              Right  Shifting  Fibonacci  (M4)                ⁢                  xe2x80x83                    
The general forms are differentiated by the location of a diagonal row of 1""s. If the LFSR is right-shifting, the companion matrix will have a diagonal row of 1""s above the main diagonal. A left-shifting LFSR has a companion matrix with a diagonal row of 1""s below the main diagonal.
A companion matrix also incorporates coefficients of a polynomial. The feedback polynomial coefficients for a Fibonacci LPSR are incorporated at the rightmost column in the left-shifting companion matrix and at the leftmost column for the right-shifting companion matrix. The characteristic polynomial coefficients for a Galois LFSR are incorporated at the top row of the left-shifting companion matrix and at the bottom row of the right-shifting companion matrix. In the Fibonacci form of M2 and M4, A0 is the coefficient for the oldest shift register element. A characteristic polynomial will have the form Cnxn+Cnxe2x88x921xnxe2x88x921+ . . . +czx2+c1x7+c0x0, while its inverse, the feedback polynomial will be of the form a0xn+a1xnxe2x88x921+ . . . +anxe2x88x922x2+anxe2x88x921x1+anx0, where cn=An; Cnxe2x88x921=Anxe2x88x921, etc.
It is well known that in order for an LFSR to have a maximal LRS period, the polynomial formed from the sequence of taps must be a primitive polynomial. A method commonly used is to choose a random polynomial and test whether it is primitive. This test is usually accomplished using a table, as useful tables of primitive polynomials have been published by many authors. period LRS consists of 2nxe2x88x921 distinct serial patterns of n bits. (A pattern with n 0""s is not used). The n bit pattern extending from each bit in the sequence is unique to the sequence. As a simple example, for n=3, the possible 3 bit combinations are 001, 010, 011, 100, 101, 110, 111. A 7 bit (23xe2x88x921) maximum length sequence is: 0111010. Working around this sequence we see all possible 3 bit combinations (other than 000) as follows: 011; 111; 110; 101; 010; 100; 001.
It is advantageous to use a polynomial with a degree that is a Mersenne prime because if such a polynomial is nonfactorable, A is also primitive, which means that the LRS is maximal length. Mersenne primes are Mersenne numbers (number of the form 2nxe2x88x921) which also happen to be prime numbers. The result of 23xe2x88x921=7 is prime, hence 23xe2x88x921 is a Mersenne prime. The result of 24xe2x88x921=15 is not hence 24xe2x88x921 is not a Mersenne prime.
Bit Error-Rate Test of Communication Channels
In order to perform rigorous testing of communication channels, pseudorandom bit patterns are generated at the transmitter. At the receiver, the received bit pattern is compared with the same pseudorandom bit sequence (generated independently at the receiver) for correctness. Because there is some communication delay between the transmitter and the receiver, some method of synchronizing the receiver pattern generator with the delayed transmitter-generated pattern is required. This is commonly done by searching the received data for a known pattern. When this pattern is found, the receiver""s generator is enabled from this known state.
Searching the received data for a known pattern requires circuitry to xe2x80x9chuntxe2x80x9d for specific unique patterns in the received data. xe2x80x9cHuntingxe2x80x9d involves additional synchronization delay because the period of the transmitted sequence may be long. With modern communications systems, the transmission occurs at much higher frequencies than the bit generation. In order to use high communication channel data rates, the sequences may also be generated in xe2x80x9cparallel,xe2x80x9d several bits at a time.
Parallelizing Encryption
Because LFSRs are serial devices, both the Galois and Fibonacci models are speed limited by the maximum clocking/shifting rate of the circuitry involved. The clocking/shifting rate is dependent upon the signal settling time of the inputs to the registers.
Parallel LRS generation theoretically will speed up sequence generation. Multiple encryption modules operating in parallel are the cornerstone of scalable encryption with linear recurring sequences.
One of the major problems with parallelizing LRS encryption is ensuring that each encryption module is getting the proper portion of the key sequence at the correct point in the encryption or decryption of the message. This problem is addressed by a method of generating linear recurring sequences by using parallel decimated sequences as disclosed by Pierson and Witzke in The Role of Decimated Sequences in Scaling Encryption Speeds Through Parallelism, Conference Proceedings of the 1996 IEEE Fifteenth Annual International Phoenix Conference on Computers and Communications, Mar. 27, 1996, pp. 515-519, which is hereby incorporated by reference.
As taught by Pierson et al., companion matrices allow manipulation of linear recurring sequences using matrix arithmetic. The pattern of 1""s and 0""s in a LFSR define a current state vector which can be multiplied mod 2 with the companion matrix to yield the xe2x80x9cnext statexe2x80x9d vector of the state machine; i.e., the vector that would be obtained by shifting the register once. The companion matrix also can be raised to a power k, corresponding to a xe2x80x9cjumpxe2x80x9d in the number of states spanned by each multiplication mod 2. This exponentiated companion matrix is called a decimation matrix. As also discussed therein, decimation allows generation of a LRS by parallel means instead of serial.
The result of Pierson et al. is illustrated with the following example: assume a linear recurring sequence of states 1-33 (where each state may be one bit). A LFSR would generate them as a series over 33 cycles. This sequence can be generated much faster by two identical parallel generators A, B (k=2), where each generator outputs 4 states each cycle (x=4). As taught by Pierson et al., the x*k=eighth decimation matrix of the companion matrix for the serial generator is used to design A and B, and they output the states in only five cycles as follows:
The parallel generators noted above which generate, in parallel, multiple bits of the same linear recurring sequence, are called Linear Recurring Sequence Generators (LRSG).
If just one 4 bit LRSG was to be utilized to generate the 33 bit LRS of the previous example, the LRSG would be designed using the fourth decimation matrix (x=4; k=1) and nine cycles would be required to generate the 33 bit LRS.
The maximum clocking rate of an LRSG is governed by the maximum number of inputs to any of its registers. More input to a register means that more layers of logic gates are required which generally results in greater propagation delay. By minimizing the number of inputs to the computation of the next state to be latched by the registers, the number of logic gates is minimized and the minimum signal settling time is achieved, thereby maximizing the permissible clocking rate. Thus it is desirable to have input circuitry that has a minimum number of inputs to any register yet still allows production of a maximal length pseudorandom sequence.
The disclosed innovations, in varying embodiments, provide one or more of the following advantages: a quick method for optimizing feedback circuits for implementing parallel generation of linear recurring sequences (LRS); a linear recurring sequence generator .(LRSG) with maximal period that is optimized for minimal feedback circuit propagation delay; a fast method for synchronizing bit error-rate testers; and a fast method for generating linear recurring sequences by parallel operation of multiple linear recurring sequence generators with feedback circuits optimized to balance minimum propagation delay against maximal sequence period.
To achieve the foregoing and other objects, and in accordance with the purpose of the present invention, as embodied and broadly described herein, the present invention may comprise a linear recurring sequence generator comprising n storage elements, each element having an input and an output, the outputs generating in parallel n bits of a linear recurring sequence. The invention further comprises a next-state generator comprising n next-state outputs, each next-state output being connected to a different one of the storage element inputs. The LSRG includes a plurality of logic gates controlling the next-state outputs, each logic gate having an input operationally connected to at least one of the storage element outputs. The connections and placement of the logic gates are a function of the nth decimation matrix of a companion matrix for a polynomial from which the linear recurring sequence would be generated in sequence, and the polynomial is selected so its companion matrix has non-zero coefficients grouped in a designated corner in order that the kth decimation matrix will have a maximum number of zeros.
A feedback circuit comprising XOR logic gates implements next state generation based on the decimation matrix in hardware. Sparse decimation matrices can be implemented with fewer XOR gates, and therefore a minimum propagation delay through the feedback circuit.